home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1995 October / EnigmA AMIGA RUN 01 (1995)(G.R. Edizioni)(IT)[!][issue 1995-10][Aminet 7].iso / Aminet / dev / gcc / ixemul_src.lha / ixemul-41.0 / gen_library / glob.c < prev    next >
C/C++ Source or Header  |  1995-05-28  |  15KB  |  598 lines
  1. /*
  2.  * Copyright (c) 1989 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Guido van Rossum.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)glob.c    5.12 (Berkeley) 6/24/91";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. /*
  42.  * glob(3) -- a superset of the one defined in POSIX 1003.2.
  43.  *
  44.  * The [!...] convention to negate a range is supported (SysV, Posix, ksh).
  45.  *
  46.  * Optional extra services, controlled by flags not defined by POSIX:
  47.  *
  48.  * GLOB_QUOTE:
  49.  *    Escaping convention: \ inhibits any special meaning the following
  50.  *    character might have (except \ at end of string is retained).
  51.  * GLOB_MAGCHAR:
  52.  *    Set in gl_flags if pattern contained a globbing character.
  53.  * gl_matchc:
  54.  *    Number of matches in the current invocation of glob.
  55.  */
  56.  
  57. #define KERNEL
  58. #include "ixemul.h"
  59. #include "kprintf.h"
  60.  
  61. #undef DEBUG
  62.  
  63. #include <sys/cdefs.h>
  64. #include <dirent.h>
  65. #include <glob.h>
  66. #include <ctype.h>
  67. #include <string.h>
  68. #include <stdio.h>
  69. #include <stdlib.h>
  70.  
  71. extern struct dirent *readdir (DIR *);
  72. extern DIR *opendir (char *);
  73.  
  74. #undef NOT    /* in <intuition/intuition.h> on AmigaDOS */
  75.  
  76. #define    DOLLAR        '$'
  77. #define    DOT        '.'
  78. #define    EOS        '\0'
  79. #define    LBRACKET    '['
  80. #define    NOT        '!'
  81. #define    QUESTION    '?'
  82. #define    QUOTE        '\\'
  83. #define    RANGE        '-'
  84. #define    RBRACKET    ']'
  85. #define    SEP        '/'
  86. #define    STAR        '*'
  87. #define    TILDE        '~'
  88. #define    UNDERSCORE    '_'
  89.  
  90. #define    M_QUOTE        0x8000
  91. #define    M_PROTECT    0x4000
  92. #define    M_MASK        0xffff
  93. #define    M_ASCII        0x00ff
  94.  
  95. #define    CHAR(c)        ((c)&M_ASCII)
  96. #define    META(c)        ((c)|M_QUOTE)
  97. #define    M_ALL        META('*')
  98. #define    M_END        META(']')
  99. #define    M_NOT        META('!')
  100. #define    M_ONE        META('?')
  101. #define    M_RNG        META('-')
  102. #define    M_SET        META('[')
  103. #define    ismeta(c)    (((c)&M_QUOTE) != 0)
  104.  
  105. typedef u_short Char;
  106.  
  107. static int     compare __P((const void *, const void *));
  108. static int     icompare __P((const void *, const void *));
  109. static void     g_Ctoc __P((Char *, char *));
  110. static int     g_lstat __P((Char *, struct stat *));
  111. static DIR    *g_opendir __P((Char *));
  112. static Char    *g_strchr __P((Char *, int));
  113. static int     g_stat __P((Char *, struct stat *));
  114. static int     glob1 __P((Char *, glob_t *));
  115. static int     glob2 __P((Char *, Char *, Char *, glob_t *));
  116. static int     glob3 __P((Char *, Char *, Char *, Char *, glob_t *));
  117. static int     globextend __P((Char *, glob_t *));
  118. static int     match __P((Char *, Char *, Char *, int));
  119. #ifdef DEBUG
  120. static void     qprintf __P((Char *));
  121. #endif
  122.  
  123. /*
  124.  * The main glob() routine: compiles the pattern (optionally processing
  125.  * quotes), calls glob1() to do the real pattern matching, and finally
  126.  * sorts the list (unless unsorted operation is requested).  Returns 0
  127.  * if things went well, nonzero if errors occurred.  It is not an error
  128.  * to find no matches.
  129.  */
  130. glob(pattern, flags, errfunc, pglob)
  131.     const char *pattern;
  132.     int flags, (*errfunc) __P((char *, int));
  133.     glob_t *pglob;
  134. {
  135.     const u_char *compilepat, *patnext;
  136.     int c, err, oldpathc;
  137.     Char *bufnext, *bufend, *compilebuf, *qpatnext, patbuf[MAXPATHLEN+1];
  138.     char *glob_pattern = (char *)pattern;
  139.  
  140.         if (index(pattern, ':'))
  141.           {
  142.             char *colon;
  143.  
  144.             glob_pattern = alloca(strlen(pattern) + 2);
  145.             strcpy(glob_pattern + 1, pattern);
  146.             *glob_pattern = '/';
  147.             colon = index(glob_pattern, ':');
  148.             *colon = '/';
  149.           }
  150.     patnext = (u_char *) glob_pattern;
  151.     if (!(flags & GLOB_APPEND)) {
  152.         pglob->gl_pathc = 0;
  153.         pglob->gl_pathv = NULL;
  154.         if (!(flags & GLOB_DOOFFS))
  155.             pglob->gl_offs = 0;
  156.     }
  157.     pglob->gl_flags = flags & ~GLOB_MAGCHAR;
  158.     pglob->gl_errfunc = errfunc;
  159.     oldpathc = pglob->gl_pathc;
  160.     pglob->gl_matchc = 0;
  161.  
  162.     bufnext = patbuf;
  163.     bufend = bufnext + MAXPATHLEN;
  164.     compilebuf = bufnext;
  165.     compilepat = patnext;
  166.     if (flags & GLOB_QUOTE) {
  167.         /* Protect the quoted characters. */
  168.         while (bufnext < bufend && (c = *patnext++) != EOS) 
  169.             if (c == QUOTE) {
  170.                 if ((c = *patnext++) == EOS) {
  171.                     c = QUOTE;
  172.                     --patnext;
  173.                 }
  174.                 *bufnext++ = c | M_PROTECT;
  175.             }
  176.             else
  177.                 *bufnext++ = c;
  178.     }
  179.     else 
  180.         while (bufnext < bufend && (c = *patnext++) != EOS) 
  181.             *bufnext++ = c;
  182.     *bufnext = EOS;
  183.  
  184.     bufnext = patbuf;
  185.     qpatnext = patbuf;
  186.     /* We don't need to check for buffer overflow any more. */
  187.     while ((c = *qpatnext++) != EOS) {
  188.         switch (c) {
  189.         case LBRACKET:
  190.             pglob->gl_flags |= GLOB_MAGCHAR;
  191.             c = *qpatnext;
  192.             if (c == NOT)
  193.                 ++qpatnext;
  194.             if (*qpatnext == EOS ||
  195.                 g_strchr(qpatnext+1, RBRACKET) == NULL) {
  196.                 *bufnext++ = LBRACKET;
  197.                 if (c == NOT)
  198.                     --qpatnext;
  199.                 break;
  200.             }
  201.             *bufnext++ = M_SET;
  202.             if (c == NOT)
  203.                 *bufnext++ = M_NOT;
  204.             c = *qpatnext++;
  205.             do {
  206.                 *bufnext++ = CHAR(c);
  207.                 if (*qpatnext == RANGE &&
  208.                     (c = qpatnext[1]) != RBRACKET) {
  209.                     *bufnext++ = M_RNG;
  210.                     *bufnext++ = CHAR(c);
  211.                     qpatnext += 2;
  212.                 }
  213.             } while ((c = *qpatnext++) != RBRACKET);
  214.             *bufnext++ = M_END;
  215.             break;
  216.         case QUESTION:
  217.             pglob->gl_flags |= GLOB_MAGCHAR;
  218.             *bufnext++ = M_ONE;
  219.             break;
  220.         case STAR:
  221.             pglob->gl_flags |= GLOB_MAGCHAR;
  222.             *bufnext++ = M_ALL;
  223.             break;
  224.         default:
  225.             *bufnext++ = CHAR(c);
  226.             break;
  227.         }
  228.     }
  229.     *bufnext = EOS;
  230. #ifdef DEBUG
  231.     qprintf(patbuf);
  232. #endif
  233.  
  234.     if ((err = glob1(patbuf, pglob)) != 0)
  235.         return(err);
  236.  
  237.     if (pglob->gl_pathc == oldpathc && flags & GLOB_NOCHECK) {
  238.         if (!(flags & GLOB_QUOTE)) {
  239.             Char *dp = compilebuf;
  240.             const u_char *sp = pattern;
  241.             while (*dp++ = *sp++);
  242.         }
  243.         else {
  244.             /*
  245.              * Copy pattern, interpreting quotes; this is slightly
  246.              * different than the interpretation of quotes above
  247.              * -- which should prevail?
  248.              */
  249.             while (*pattern != EOS) {
  250.                 if (*pattern == QUOTE) {
  251.                     if (*++pattern == EOS)
  252.                         --pattern;
  253.                 }
  254.                 *compilebuf++ = (u_char)*pattern++;
  255.             }
  256.             *compilebuf = EOS;
  257.         }
  258.         return(globextend(patbuf, pglob));
  259.     } else if (!(flags & GLOB_NOSORT)) 
  260.         qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc,
  261.             pglob->gl_pathc - oldpathc, sizeof(char *),
  262.                     (flags & GLOB_NOCASE) ? icompare : compare);
  263.     return(0);
  264. }
  265.  
  266. static int
  267. compare(p, q)
  268.     const void *p, *q;
  269. {
  270.     return(strcmp(*(char **)p, *(char **)q));
  271. }
  272.  
  273. static int
  274. icompare(p, q)
  275.     const void *p, *q;
  276. {
  277.     return(strcasecmp(*(char **)p, *(char **)q));
  278. }
  279.  
  280. static
  281. glob1(pattern, pglob)
  282.     Char *pattern;
  283.     glob_t *pglob;
  284. {
  285.     Char pathbuf[MAXPATHLEN+1];
  286.  
  287.     /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */
  288.     if (*pattern == EOS)
  289.         return(0);
  290.     return(glob2(pathbuf, pathbuf, pattern, pglob));
  291. }
  292.  
  293. /*
  294.  * The functions glob2 and glob3 are mutually recursive; there is one level
  295.  * of recursion for each segment in the pattern that contains one or more
  296.  * meta characters.
  297.  */
  298. static
  299. glob2(pathbuf, pathend, pattern, pglob)
  300.     Char *pathbuf, *pathend, *pattern;
  301.     glob_t *pglob;
  302. {
  303.     struct stat sb;
  304.     Char *p, *q;
  305.     int anymeta;
  306.  
  307.     /*
  308.      * Loop over pattern segments until end of pattern or until
  309.      * segment with meta character found.
  310.      */
  311.     for (anymeta = 0;;) {
  312.         if (*pattern == EOS) {        /* End of pattern? */
  313.             *pathend = EOS;
  314.             if (g_stat(pathbuf, &sb))
  315.                 return(0);
  316.         
  317.             if (((pglob->gl_flags & GLOB_MARK) &&
  318.                 pathend[-1] != SEP) && (S_ISDIR(sb.st_mode)
  319.                 || (S_ISLNK(sb.st_mode) &&
  320.                 (g_stat(pathbuf, &sb) == 0) &&
  321.                 S_ISDIR(sb.st_mode)))) {
  322.                 *pathend++ = SEP;
  323.                 *pathend = EOS;
  324.             }
  325.             ++pglob->gl_matchc;
  326.             return(globextend(pathbuf, pglob));
  327.         }
  328.  
  329.         /* Find end of next segment, copy tentatively to pathend. */
  330.         q = pathend;
  331.         p = pattern;
  332.         while (*p != EOS && *p != SEP) {
  333.             if (ismeta(*p))
  334.                 anymeta = 1;
  335.             *q++ = *p++;
  336.         }
  337.  
  338.         if (!anymeta) {        /* No expansion, do next segment. */
  339.             pathend = q;
  340.             pattern = p;
  341.             while (*pattern == SEP)
  342.                 *pathend++ = *pattern++;
  343.         } else            /* Need expansion, recurse. */
  344.             return(glob3(pathbuf, pathend, pattern, p, pglob));
  345.     }
  346.     /* NOTREACHED */
  347. }
  348.  
  349. static
  350. glob3(pathbuf, pathend, pattern, restpattern, pglob)
  351.     Char *pathbuf, *pathend, *pattern, *restpattern;
  352.     glob_t *pglob;
  353. {
  354.     register struct dirent *dp;
  355.     DIR *dirp;
  356.     int len, err;
  357.  
  358.     *pathend = EOS;
  359.     errno = 0;
  360.     KPRINTF (("&errno = %lx, errno = %ld\n", &errno, errno));
  361.         
  362.     if (!(dirp = g_opendir(pathbuf)))
  363.         /* TODO: don't call for ENOENT or ENOTDIR? */
  364.         if (pglob->gl_errfunc &&
  365.             (*pglob->gl_errfunc)(pathbuf, errno) ||
  366.             (pglob->gl_flags & GLOB_ERR))
  367.             return(GLOB_ABEND);
  368.         else
  369.             return(0);
  370.  
  371.     err = 0;
  372.  
  373.     /* Search directory for matching names. */
  374.     while ((dp = readdir(dirp))) {
  375.         register u_char *sc;
  376.         register Char *dc;
  377.  
  378.         /* Initial DOT must be matched literally. */
  379.         if (dp->d_name[0] == DOT && *pattern != DOT)
  380.             continue;
  381.         for (sc = (u_char *) dp->d_name, dc = pathend; 
  382.              *dc++ = *sc++;);
  383.         if (!match(pathend, pattern, restpattern, pglob->gl_flags & GLOB_NOCASE)) {
  384.             *pathend = EOS;
  385.             continue;
  386.         }
  387.         err = glob2(pathbuf, --dc, restpattern, pglob);
  388.         if (err)
  389.             break;
  390.     }
  391.  
  392.     /* TODO: check error from readdir? */
  393.     (void)closedir(dirp);
  394.     return(err);
  395. }
  396.  
  397.  
  398. /*
  399.  * Extend the gl_pathv member of a glob_t structure to accomodate a new item,
  400.  * add the new item, and update gl_pathc.
  401.  *
  402.  * This assumes the BSD realloc, which only copies the block when its size
  403.  * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
  404.  * behavior.
  405.  *
  406.  * Return 0 if new item added, error code if memory couldn't be allocated.
  407.  *
  408.  * Invariant of the glob_t structure:
  409.  *    Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
  410.  *    gl_pathv points to (gl_offs + gl_pathc + 1) items.
  411.  */
  412. static int
  413. globextend(path, pglob)
  414.     Char *path;
  415.     glob_t *pglob;
  416. {
  417.     register char **pathv;
  418.     register int i;
  419.     u_int newsize;
  420.     char *copy;
  421.     Char *p;
  422.  
  423.     newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs);
  424.     pathv = (char **)realloc((char *)pglob->gl_pathv, newsize);
  425.     if (pathv == NULL)
  426.         return(GLOB_NOSPACE);
  427.  
  428.     if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) {
  429.         /* first time around -- clear initial gl_offs items */
  430.         pathv += pglob->gl_offs;
  431.         for (i = pglob->gl_offs; --i >= 0; )
  432.             *--pathv = NULL;
  433.     }
  434.     pglob->gl_pathv = pathv;
  435.  
  436.     for (p = path; *p++;);
  437.     if ((copy = malloc(p - path)) != NULL) {
  438.         g_Ctoc(path, copy);
  439.         pathv[pglob->gl_offs + pglob->gl_pathc++] = copy;
  440.     }
  441.     pathv[pglob->gl_offs + pglob->gl_pathc] = NULL;
  442.     return(copy == NULL ? GLOB_NOSPACE : 0);
  443. }
  444.  
  445.  
  446. /*
  447.  * pattern matching function for filenames.  Each occurrence of the *
  448.  * pattern causes a recursion level.
  449.  */
  450. static
  451. match(name, pat, patend, nocase)
  452.     register Char *name, *pat, *patend;
  453.     register int nocase;
  454. {
  455.     int ok, negate_range;
  456.     Char c, k;
  457.  
  458.     while (pat < patend) {
  459.         c = *pat++;
  460.         switch (c & M_MASK) {
  461.         case M_ALL:
  462.             if (pat == patend)
  463.                 return(1);
  464.             for (; *name != EOS; ++name)
  465.                 if (match(name, pat, patend, nocase))
  466.                     return(1);
  467.             return(0);
  468.         case M_ONE:
  469.             if (*name++ == EOS)
  470.                 return(0);
  471.             break;
  472.         case M_SET:
  473.             ok = 0;
  474.             k = *name++;
  475.             if (nocase)
  476.               k = tolower(k);
  477.             if (negate_range = ((*pat & M_MASK) == M_NOT))
  478.                 ++pat;
  479.             while (((c = *pat++) & M_MASK) != M_END) {
  480.                     if (nocase)
  481.                             c = tolower(c);
  482.                 if ((*pat & M_MASK) == M_RNG) {
  483.                     if (c <= k && k <= (nocase ? tolower(pat[1]) : pat[1]))
  484.                         ok = 1;
  485.                     pat += 2;
  486.                 } else if (c == k)
  487.                     ok = 1;
  488.                         }
  489.             if (ok == negate_range)
  490.                 return(0);
  491.             break;
  492.         default:
  493.                 if (nocase)
  494.                 {
  495.                   k = *name++;
  496.                   if (tolower(k) != tolower(c))
  497.                     return 0;
  498.                 }
  499.             else if (*name++ != c)
  500.                 return(0);
  501.             break;
  502.         }
  503.     }
  504.     return(*name == EOS);
  505. }
  506.  
  507. /* Free allocated data belonging to a glob_t structure. */
  508. void
  509. globfree(pglob)
  510.     glob_t *pglob;
  511. {
  512.     register int i;
  513.     register char **pp;
  514.  
  515.     if (pglob->gl_pathv != NULL) {
  516.         pp = pglob->gl_pathv + pglob->gl_offs;
  517.         for (i = pglob->gl_pathc; i--; ++pp)
  518.             if (*pp)
  519.                 free(*pp);
  520.         free(pglob->gl_pathv);
  521.     }
  522. }
  523.  
  524. static DIR *
  525. g_opendir(str)
  526.     register Char *str;
  527. {
  528.     char buf[MAXPATHLEN];
  529.  
  530.     if (!*str)
  531.         return(opendir("."));
  532.     g_Ctoc(str, buf);
  533.     return(opendir(buf));
  534. }
  535.  
  536. static int
  537. g_lstat(fn, sb)
  538.     register Char *fn;
  539.     struct stat *sb;
  540. {
  541.     char buf[MAXPATHLEN];
  542.  
  543.     g_Ctoc(fn, buf);
  544.     return(lstat(buf, sb));
  545. }
  546.  
  547. static int
  548. g_stat(fn, sb)
  549.     register Char *fn;
  550.     struct stat *sb;
  551. {
  552.     char buf[MAXPATHLEN];
  553.  
  554.     g_Ctoc(fn, buf);
  555.     return(stat(buf, sb));
  556. }
  557.  
  558. static Char *
  559. g_strchr(str, ch)
  560.     Char *str;
  561.     int ch;
  562. {
  563.     do {
  564.         if (*str == ch)
  565.             return (str);
  566.     } while (*str++);
  567.     return (NULL);
  568. }
  569.  
  570. static void
  571. g_Ctoc(str, buf)
  572.     register Char *str;
  573.     char *buf;
  574. {
  575.     register char *dc;
  576.  
  577.     for (dc = buf; *dc++ = *str++;);
  578. }
  579.  
  580. #ifdef DEBUG
  581. static void 
  582. qprintf(s)
  583.     register Char *s;
  584. {
  585.     register Char *p;
  586.  
  587.     for (p = s; *p; p++)
  588.         (void)printf("%c", *p & 0xff);
  589.     (void)printf("\n");
  590.     for (p = s; *p; p++)
  591.         (void)printf("%c", *p & M_PROTECT ? '"' : ' ');
  592.     (void)printf("\n");
  593.     for (p = s; *p; p++)
  594.         (void)printf("%c", *p & M_META ? '_' : ' ');
  595.     (void)printf("\n");
  596. }
  597. #endif
  598.